import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 
 * 完全二叉树
 * 
 * 
 */
public class 二叉树遍历 {
   
    public static void main(String[] args) {
        
        TN root = new TN(1);
        root.left = new TN(2);
        root.left.left = new TN(4);
        root.left.left.right = new TN(6);
        root.left.left.right.left = new TN(7);
        root.left.left.right.right = new TN(8);
        root.right = new TN(3);
        root.right.right = new TN(5);

        //先序遍历
        LinkedList<Integer> resultList;
        System.out.println("先序遍历");
        preForEach(root, resultList = new LinkedList<>());
        resultList.stream().map(s -> s+ ", ").forEach(System.out::print);
        System.out.println();

        System.out.println("中序遍历");
        middleForEach(root, resultList = new LinkedList<>());
        resultList.stream().map(s -> s+ ", ").forEach(System.out::print);
        System.out.println();

        System.out.println("后序遍历");
        afterForEach(root, resultList = new LinkedList<>());
        resultList.stream().map(s -> s+ ", ").forEach(System.out::print);
        System.out.println();
        
        System.out.println("层序遍历");
        levelForEach(root, resultList = new LinkedList<>());
        resultList.stream().map(s -> s+ ", ").forEach(System.out::print);
        System.out.println();

    }

    //先序遍历
    private static void preForEach(TN root, LinkedList resultList){

        if(null != root){

            resultList.add(root.value);
            preForEach(root.left, resultList);
            preForEach(root.right, resultList);
        }

    }

    //中序遍历
    private static void middleForEach(TN root, LinkedList resultList){
        if(null != root){

            middleForEach(root.left, resultList);
            resultList.add(root.value);
            middleForEach(root.right, resultList);

        }
    }

    //后序遍历
    private static void afterForEach(TN root, LinkedList resultList){
        if(null != root){


            afterForEach(root.left, resultList);
            afterForEach(root.right, resultList);
            resultList.add(root.value);

        }
    }

    //层序遍历
    private static void levelForEach(TN root, LinkedList resultList){

        if(null!=root){

            Queue<TN> queue = new LinkedList<>();

            queue.add(root);

            while (!queue.isEmpty()) {
            

                TN temp = queue.poll();

                resultList.add(temp.value);

                if(null!=temp.left) queue.add(temp.left);
                if(null!=temp.right) queue.add(temp.right);


            }
        }
    }

    private static class TN{

        int value;

        TN left;

        TN right;

        public TN(int value){

            this.value = value;
        }

    }
}
